P1891 疯狂LCM

i=1nlcm(i,n)\sum_{i=1}^n lcm(i,n)

i=1ningcd(i,n)\sum_{i=1}^n \frac{i*n}{gcd(i,n)}

ni=1nigcd(i,n)n\sum_{i=1}^n \frac{i}{gcd(i,n)}

ndni=1n[gcd(i,n)=d]idn\sum_{d|n}\sum_{i=1}^n [gcd(i,n)=d]\frac{i}{d}

ndni=1nd[gcd(i,nd)=1]in\sum_{d|n}\sum_{i=1}^{\frac{n}{d}} [gcd(i,\frac{n}{d})=1]i

ndni=1d[gcd(i,d)=1]in\sum_{d|n}\sum_{i=1}^{d} [gcd(i,d)=1]i

f(n)=i=1ni[gcd(i,n)=1],g(n)=inf(i)f(n)=\sum_{i=1}^ni[gcd(i,n)=1] , g(n)=\sum_{i|n} f(i)

f(n)=12i=1ni[gcd(i,n)=1]+(ni)[gcd(ni,n)=1]f(n)=\frac{1}{2} \sum_{i=1}^n i[gcd(i,n)=1]+(n-i)[gcd(n-i,n)=1]

=12i=1nn[gcd(i,n)=1]=\frac{1}{2} \sum_{i=1}^n n[gcd(i,n)=1]

=n2i=1n[gcd(i,n)=1]=\frac{n}{2} \sum_{i=1}^n [gcd(i,n)=1]

=n×φ(n)2=\frac{n \times \varphi(n)}{2}

枚举因数预处理 g(n)g(n),注意一下 f(1)=1f(1)=1

答案为:n×g(n)n \times g(n)

#include <cstdio>

const int MAXN = 1000000;
int t , n , k , prime[ MAXN + 5 ] , phi[ MAXN + 5 ];
long long g[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( ) {
	phi[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			phi[ i ] = i - 1;
		}
		for( int j = 1 ; j <= k && i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) {
				phi[ i * prime[ j ] ] = phi[ i ] * prime[ j ];
				break;
			}
			phi[ i * prime[ j ] ] = phi[ i ] * ( prime[ j ] - 1 );
		}
	}

	for( int i = 1 ; i <= MAXN ; i ++ )
		for( int j = i ; j <= MAXN ; j += i )
			g[ j ] += i == 1 ? 1 : 1ll * phi[ i ] * i / 2;
}

int main( ) {
	sieve( );
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d",&n);
		printf("%lld\n", n * g[ n ] );
	}
	return 0;
}